/**
 * 从第一行任意一个出发，可以走到下一行的三个格子
 * 且要求路径必须严格递增，问能够走的步数，即路径长度减一
 * 
 */
class Solution {

using vi = vector<int>;

enum {None = -1};

vector<vi> *pData;
vector<vi> D;
int N;
int M;

public:
    int maxMoves(vector<vector<int>>& grid) {
        pData = &grid;
        N = pData->size();
        M = pData->back().size();
        D.assign(N, vi(M, None));
        int ans = None;
        for(int i=0;i<N;++i){
            chkmax(ans, dp(i, 0));
        }
        return ans;        
    }

    int dp(int r, int c){
        if(None != D[r][c]) return D[r][c];
        if(c + 1 == M) return D[r][c] = 0;

        int ans = None;
        for(int i=r-1;i<=r+1;++i){
            if(0 <= i and i < N and (*pData)[r][c] < (*pData)[i][c + 1]){
                chkmax(ans, dp(i, c + 1));
            }
        }
        if(ans == None) return D[r][c] = 0;
        return D[r][c] = ans + 1;
    }

    void chkmax(int & d, int a){
        if(None == a) return;
        if(d == None or d < a) d = a;
    }

};
